#include <string>
#include <iostream>
using namespace std;

struct Tnode
{
    string word;
    int count;
    Tnode* left;
    Tnode* right;
};
//When coding, I refact  some vars, causing lots of problem.
void add_node(Tnode*& head, const string& word)
{
    if(0 == head){
        head = new Tnode();
        head->word = word;
        head->count = 1;
        head->left = head->right = 0;
    }else{
        Tnode* pnode = head;
        for(;;){
            int ret = word.compare(pnode->word);
            if(ret == 0){
                ++(pnode->count);
                return;
            }
            else{
                Tnode** p = (ret > 0) ? &pnode->right:&pnode->left;
                if(*p == 0){
                    Tnode* newp = new Tnode();
                    newp->word = word;
                    newp->count = 1;
                    newp->left = newp->right = 0;
                    *p = newp;
                    return;
                }else{
                    pnode = *p;
                }
            }
        }        
    }
}
void print_nodes(const Tnode* head)
{
    if(head){
        print_nodes(head->left);
        cout << head->word << " " << head->count << endl;
        print_nodes(head->right);
    }
}
int main()
{
    Tnode* head = 0;
    add_node(head,"zhu");
    add_node(head,"zhu");
    add_node(head,"ou");
    add_node(head,"wu");
    add_node(head,"ou");
    add_node(head,"Yuan");
    add_node(head,"yue");
    add_node(head,"ma");
    add_node(head,"li");
    
    print_nodes(head);
}
